package com.chj.lintcode.backpack;

public class Code09_BackpackIX {
	/**
	 * @param n: Your money
	 * @param prices: Cost of each university application
	 * @param probability: Probability of getting the University's offer
	 * @return: the highest probability
	 */
	public static double backpackIX(int n, int[] prices, double[] probability) {
		// write your code here
		// 计算一个offer都收不到的概率，然后减掉
		// 每个offer都有收或不收两种选择，0-1背包
		// 确定状态：dp[i][j] = 在i所学校中，花费j元，一个offer都收不到的最小概率
		// 转移方程：dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - prices[i]] * (1 -
		// probability[i])) 不申请当前学校vs申请当前学校
		// 初始条件&边界情况：dp[0][0] = 1.0, j == 0, dp = 1.0, i == 0, dp = 1.0

		double[][] dp = new double[prices.length + 1][n + 1];

		for (int i = 0; i <= prices.length; i++) {
			for (int j = 0; j <= n; j++) {
				if (i == 0 || j == 0)
					dp[i][j] = 1.0;
				else {
					dp[i][j] = dp[i - 1][j]; // 不申请当前学校
					if (j >= prices[i - 1]) { // 可申请当前学校
						dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - prices[i - 1]] * (1 - probability[i - 1]));
					}
				}
			}
		}

		return 1 - dp[prices.length][n];
	}

//	https://juejin.cn/post/6875966041604751368#heading-18
//	https://juejin.cn/post/6875966041604751368#heading-13
//	https://blog.csdn.net/qq_xuanshuang/article/details/104031793
//	https://www.lintcode.com/problem/backpack-ix/note/198053
	public static void main(String[] args) {
		{
			int n = 10;
			int[] prices = { 4, 4, 5 };
			double[] probability = { 0.1, 0.2, 0.3 };
			System.out.println(backpackIX(n, prices, probability));
		}

		{
			int n = 10;
			int[] prices = { 4, 5, 6 };
			double[] probability = { 0.1, 0.2, 0.3 };
			System.out.println(backpackIX(n, prices, probability));
		}
	}
}
